home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Macintosh Common Lisp Related / User Contributions / zebu v3.3.3 (LALR parser) / doc / Zebu_intro.dvi < prev    next >
Encoding:
Text File  |  1994-09-12  |  53.2 KB  |  69 lines  |  [TEXT/ttxt]
  1. ˜Éí¿;Ë TeX output 1994.05.26:1646ãˇˇˇˇ†l熽ª†'熲&çëBçlÛL÷ΔGÆGÆcmss17ÎLZebuÛ=D”ÌtGÆGÆcmr17Ë:ë¨Añ7tT법VoöséolìforìSpòecifyingìRevêåqersibleìLALR(1)éüçí“~”Pêåqarserséüçççççë|QÛ/X´Q cmr12⁄Joacï¨rhimõÍ®Laubscìhò(laubscìh@hplabs.hp.com)éééééüfjçí…ÑMaê¨ryñÍ®26,ì1994éü$çí◊!KÛt â:        cmbx9≈Abstractéü¨—çëefl˙ÛM“o«w        cmss9ÎMZebuççü¸-=ÛπAa®cmr6∞1ééë[Ûo¥ã«        cmr9¡isñ0`partìofìaìsetìofìtoêA«olsìforìtheìtranslationìofìformalìlanguages.é§ çëXÎMZebuñD;¡conöæ9tainsìaìLALR(1)ìparserìgeneratorìlikòeìYëˇ:´accìdoêA«es.ë÷ΩAsideìfromìgen-é°çëXeratingñtaìparser,ëîHÎMZebuì¡willìalsoìgenerateìtheìinïæ9vìerseñtofìaìparserì(unparser).é°çëXInñÔbconöæ9trastìtoìYëˇ:´acc,ëˆ˘theìsemanòticsìisìnotìgivòenìinìtermsìofì\routines"ìbuté°çëXdeclarativöæ9elyñTinìtermsìofìtòypêA«edìfeatureìstructures.é°çëefl˙Theñê¸abilitöæ9yìtoìdeclarativòelyìde neìaìrevòersibleìgrammar,ë´ttogetherìwithé°çëXañrewrite-ruleìmecöæ9hanismì(ÎMZebu-RR¡)ëïforìtransformingìabstractìsynòtaxé°çëXtreesñ≠ÆconstituteìtheìbasicìtoöA«olsìforìspòecifyingìtranslatorsìforìformalìlan-é°çëXguages.éüó¸çëXÛ"Ú"V
  3. cmbx10ÕKeywêÆ9ordsë    ?¸¡Fëˇ:´ormalë8language,ñBÿLALR-grammar,ìparsing,ìtranslation,ìgen-é°çëXeration,õTinïæ9teropêA«erabilitìyñˇ:´,òLEX,òYìAêæ9CC.éü!ƒççë?Û;Ú"Vff
  4. cmbx10Ê1éëW÷ˇInêä=troêu¬ductionéüÁçë?ÛKÒ`y
  6. cmr10»Ourñ∏goalìisìtoìdevö∏„elopìanìenòvironmenòtìforìtheìdesign,ë◊}analysisìandìmanipulationé§ çë?ofñøÃformalìlanguages,õ⁄jsucê∏„hìasìprogrammingìlanguages,òmarkupìlanguages,òdataé°çë?inï∏„tercìhangeñ∞¯formatsìorìknoö∏„wledgeìrepresenòtationìlanguagesì(sucòhìasìtheìtransla-é°çë?tionñ¥ºtoìandìfromìKIF)ë¥ì[Õ?»].ë<?Beingìableìtoìdesign,ñ‘€analyze,ìandñ¥ºmanipulateìformalé°çë?languagesñ√¢isìcrucialìforìacö∏„hievingìsoftòwòareìinòteropêGerabilitòyì[Õ?»],ëfl5automaticìcoêGdeé°çë?analysis,ñ◊∞indexing,ìandñΩûretrievëˇq«alìforìpöGotenê∏„tialìreuse.ë™°Zebuìhasìbòeenìappliedìtoé°çë?writingñHÏtranslatorsìforìformalìlanguagesì[Õ?»].ëm§Theìmainìideaìofìthisìwê∏„orkìisìthaté°çë?añïÈmoêGduleìÛ †b>
  8. cmmi10…mì»commö∏„unicatesìbòyìsendingìorìreceivingìmessagesìinìsomeìlanguageé°çë?…L»(…m»),ëu'andñ;óthatìforìvëˇq«ariousìreasonsìdi erenö∏„tìmoêGdulesìuseìdi erenòtìlanguages.éë?üÊfâffâˇvü    J=çççë "5ü˝-:∞1ééëL‹Û|{Ycmr8ª\ÛN2«@…cmbx8ÎNzebuÛ#—fêcmti8ænª.,ñ3›æplª.õ©¯ÎN-busª,ìÎN-buª:ë^Z1.òanõ ıoï√éxlikìeòdomesticòanimalò(æBosëX≈indicusª)ònativìeòtoòAsiaòand駠   Äçpartsñ≈^ofìAfrica:ëø#itìhasìaìlargeìhö√éumpìoòvòerìtheìshoulders,ñ»êshort,ìcurvingõ≈^horns,ìpê<rendulousòears,é°çandñªëaìlargeìdewlapìandìisìresistanê√étìtoìheatìandìinsect-bê<rornìdeseases."ëæà[WõˇJ™ebster'sìNewìWòorldé°çDictionaryëˇJ™.]ëΔ⁄Añ‘Özebuìshouldìnotìbê<reìconfusedìwithìaìyö√éaccìorìaìgnòuìalthoughìitìbê<rearsìsimilaritòyé°çtoñ’Xeacê√éhìofìthem.ééüçíÈ»1ééåã*†l熽ª†'熽¸çë?»Fëˇ*™orñ ¢commö∏„unicationìtoìbêGeìsuccessful,ë`translatorsìhaòvòeìtoìbêGeìused.ëY6Û$m#ΩR
  10. cmss10œZebuì»proòvidesé§ çë?toêGolsñUUtoìde neìtranslatorsìatìaìhighìlevê∏„elìofìabstractionççü¸^ˇÛ
  11. Ÿì†Rcmr7µ2ééë|s».é°çëNMcCarthï∏„yõ}finìtroêGducedòtheònotionòofò\abstract"òandò\concrete"òsynìtax.ëÈ˙Theé°çë?concreteñï)synê∏„taxìdescribêGesìtheìsurfaceìformìofìaìlinguisticìexpression,ë•whileìtheé°çë?abstractñ‘îsynê∏„taxìdescriböGesìaì(compòosite)ìobëé8ject.ñF‹E.g.ì\1+a"ñ‘îisìtheìsurfaceìstringé°çë?renderedñƒbö∏„yìaìparticularìconcreteìsynòtaxìforìanìobëé8jectìdescribêGedìbòyìanìabstracté°çë?synö∏„tax:ëàcanñ‡£additionìopêGerationìwithìtòwòoìopöGerands,ëwtheì rstìbòeingìtheìnê∏„umeralé°çë?\1",ñUUandìtheìsecondìbêGeingìtheìvëˇq«ariableìnamedì\a".é°çëNManipulationñ˛ ofìlinguisticìexpressionsìisìmï∏„ucìhñ˛ easierìtoìexpressìinìtheìab-é°çë?stractñUUsynö∏„taxìthanìinìtheìconcreteìsynòtax.é°çëNIfñãwö∏„eìwòereìtoìdesignìanìalgorithmìforìsimplifyingìexpressionsìofìsomeìlan-é°çë?guageñR|ìsaö∏„yì\arithmetic"ì|ìwòeìwòouldìuseìasìtheìfronòtìendìtheì\arithmetic-é°çë?parser"ñ…fltoìtranslateìinö∏„toìabstractìsynòtax,ëÁthenìexpressìtheìsimpli cationìrulesé°çë?inñú∏termsìofìtreeìtransformationìrulesìthatìopêGerateìonìtheìabstractìsynê∏„tax,ëÆëandé°çë? nallyñUUaddìasìtheìbacê∏„k-endìtheì\arithmetic-unparser".é°çëNMoreñqƒgeneralllyëˇ*™,ëxflifìwö∏„eìwòereìtoìdesignìanìalgorithmìforìtranslatingìfromìlan-é°çë?guageñ⁄AëŸtoìlanguageìB,ìwö∏„eìwòouldìde neìrevòersibleìgrammarsìforìlanguagesìAé°çë?andñºB,ìandìsetsìofìrewriteìrulesìtoìtransformìtheìabstractìsynê∏„taxìtreesìfromìtheé°çë?domainñÍ0ofìlanguageìAëÍtoìtheìdomainìofìlanguageìB.ìTheìfronö∏„tìendìwòouldìbêGeìtheé°çë?\A-parser"ñUUandìtheìbacê∏„k-endìtheì\B-unparser"é°çëNTheñ2›wê∏„orkìdescriböGedìinìthisìrepòortìoö∏„wsìaìlotìtoìtheìpioneeringìresearcòhìaté°çë?KestrelñÓT[Õ?»]õOrthatìresultedìinìtheìœRe neççü¸^ˇµ3ééëj«»programìtransformationìsystemì[Õ?»].òTheé°çë?basicñ3òideasìunderlyingìœZebuì»areìalreadyìpresenö∏„tìinìœRe ne».ëfàœZebuì»isìaìmòucòhìmoreé°çë?compactñï˜sytemìthanìRe neì(itìrunsìonìaìMacInö∏„toshìinìMacInòtoshìCommoné°çë?Lisp),ë≤÷andñltheìsemanö∏„ticsìisìexpressedìinìtòypêGedìfeatureìstructures.ë∏òœZebuì»alsoé°çë?o ersñPÿtheìpêGossibilitö∏„yìofìde ningìaìmeta-grammar.ëpHœZebuì»lacòksìœRe ne»'sìabilitòyìtoé°çë?declarativê∏„elyñUUspêGecifyìtransformationsìusingìaìpatternìlanguage.ççëq«ü¸^ˇµ4ééé°çëN»Theñ6ÄLALR(1)ìparsingìtableìgeneratedìbö∏„yìœZebuì»folloòwsìalgorithmsìdescribêGedé°çë?inñ—[Õ?»]õ‰Ùorì[Õ?»].òTheìcurrenö∏„tìimplemenòtationìwòasìdevòelopêGedìfromìtheìœSchemeé°çë?»programñUUdevö∏„elopêGedìbòyìWilliamìWëˇ*™ellsìandìisìwrittenìinìœCommonìLisp».é°çëNTheñcnextìsectionìwillìexplainìhoö∏„wìaìgrammarìcanìbêGeìde ned,ëìåandìhoòwìseman-é°çë?ticsñ#RcanìböGeìassoòciatedìwithìaìgrammarìrule.õaSectionìÕ??ò»describêGesìtheìde nitioné°çë?ofñk*theìsemanö∏„ticìdomain.ë≥EWithìthisìcapabilitòyìitìisìpêGossibleìtoìstateìdeclara-é°çë?tivö∏„elyñÌRwhatìtheìabstractìsynòtaxìshouldìloêGokìlikòe.õOSectionìÕ??ò»describêGesìaìsimpleré°çë?grammarñü+notationìthatìisìvê∏„eryìcloseìtoìordinaryìBNF.ìSectionìÕ??ëOH»summarizesé°çë?theñùfunctionalìinö∏„terfaceìofìZebuìandìexplainsìhoòwìaìparserìcanìbêGeìcustomized.é°çë?TheñaTlastìcö∏„hapterìdescribêGes,ë§ThoòwìlexicalìanalysisìcanìbêGeìde nedìusingìregularé°çë?expressionsñUUandìparameterization.éë?üX-âffâˇvü    J=çççë "5ü˝-:∞2ééëL‹ªTheññrewrite-ruleìmecö√éhanismì(Zebu-RR)ëï˛isìimplemenòted,ë¢∂andìwillìbö<reìdescribòedìinìaìfutureé©    Äçrepê<rort.駠   ä>çççë "5ü˝-:∞3ééëL‹ÛOΔs6ëcmss8ÎORe neñ’XªisìaìtrademarkìofìReasoningìSystems,ìPê√éaloìAlto.é°çççë "5ü˝-:∞4ééëL‹ÎOZebuñ‡ ªcanìbê<reìobtainedìviaìanonê√éymousìftpìfromìhplabsz.hpl.hp.comì(15.0.152.161)ìasìaé¶çcompressedñ’Xtarì le:ñ« pub/zebu-???.tar.gz.ìItñ’Xconö√étainsìsevòeralìexampleìgrammarìde nitions.ééüçíÈ»2ééåã ∫†l熽ª†'熽¸ççë?Ê2éëW÷ˇTheñÖRepresenêä=tationsìofìGrammarsìinìFileséüÁççë?Û4¬÷N† cmbx12fl2.1éë]¿GrammarëÄnotationéüuTçë?»Wëˇ*™eñRk rstìdescriböGeìtheìnï∏„ull-grammar,ëë∞whicìhñRkisìaìpòoï∏„wìerfullñRkbutìvê∏„erbòoseìwï∏„aìyëRktoé§ çë?spöGecifyñÛJaìgrammar.ëK•Onlyìaìparserìandìoptionallyìaìdomainìwillìbòeìgeneratedé°çë?butñAIanìunparserì(prinö∏„ter)ìwillìnot.ëkIfìthisìisìdesired,ëELyòouìmòustìuseìtheìnotationé°çë?ofñUUtheìmeta-grammarì"zebu-mg"ìwhicê∏„hìisìdescribêGedìinìsectionìÕ??».é°çëNNon-terminalsñ‘*areìrepresenö∏„tedìbòyìsymòbêGols,ë3flterminalsì(alsoìreferredìtoìasé°çë?kï∏„eywìords)õUUbìyòstrings.ëq«ThereòareòtheòfolloìwingòopêGenòclassesòofònon-terminalsççü¸^ˇµ5ééë|s»:é©˙ççëO™ÆÛ#flÍ<x
  13. cmtt10ŒidentifierñUU»::=çìÛ!",ö
  15. cmsy10 h»lispìsymê∏„bêGol iééé°ççëO™ÆŒnumberëUI»::=çëUU h»inê∏„teger iééé°ççëO™ÆŒkeywordëL»::=çëUU h»string iééé°ççë?»whereéé°çççëO™Æ h»inê∏„teger iéëxá$»::=çëUU h»digit iéëw»*éé°çççëO™Æ h»string iéës‹z»::=ñUU"çì h»cê∏„haracter iéë3qû*ì"éé¶çëNAçëfi h»lispëUUsymê∏„bêGol iéë@ Ñ»maö∏„yñfi3bêGeìquali edìbòyìaìpacòkëˇq«ageìname,ëje.g.ë `Œzb:cons-1-3ì»isé°çë?añ    ’vëˇq«alidìidenö∏„ti er.ëèHInìcaseìpacòkëˇq«agesìshouldìbêGeìdisalloòwòedìduringìlexicalìanaly-é°çë?sis,ë.‰theñavëˇq«ariableìŒ*disallow-packages*ì»shouldìböGeìbòoundìtoìÛ ˝':
  17. cmti10Àtrue».ë{Í(Itìdefaultsé°çë?toñsÀfalse»).ëÀTheìalphabêGeticìcaseìofìaìkï∏„eywìordñsisìnotìsigni canê∏„tìifìtheìvëˇq«ariableé°çë?Œzb:*case-sensitive*ñUU»isìÀfalseì»(theìdefault)ìwhenìtheìgrammarìisìloaded.é°çëNIfñ˘›alphaböGeticìcaseìofìidenê∏„ti ersìisìtoìbòeìpreservê∏„ed,ëb˛Œzb:*preserve-case*é°çë?»shouldñ¿böGeìsetìtoìÀtrue».ë∂Otherìcategoriesìcanìbòeìde nedìasìregularìexpressionsé°çë?(seeëUUÕ??»).éü˝.ççë?Õ2.1.1éëb#ÇGrammarë’TRuleséüuTçë?GrammarñEKRuleìSynêÆ9taxë
  18. »Aë∂ôgrammarñ∂≤ leìconsistsìofìaìheaderì(theì\optionsé°çë?list",ëπseeñ‰ sectionìÕ??»)ëÍfolloï∏„wìedõ‰ bìyòoneòoròmoreòdomainòde nitionsòorògrammaré°çë?rules.ëÁTheñçµnon-terminalìde nedìbê∏„yìtheì rstìgrammarìruleìisìalsoìtheìÀstart-é°çë?symbëˇ}'olñ+x»ofìtheìgrammar.ëc”Aë+nparserìwillìacceptìexactlyìtheìstringsìthatìrewriteìtoé°çë?theëUUÀstart-symbëˇ}'ol».é°çëNThisñø˝exampleìshoö∏„wsìhoòwìaìBNF-likòeìruleìcanìböGeìencoòdedìasìaìœZebuì»grammaré°çë?ruleñUU(usingìtheìnê∏„ull-grammar):éü˚4çëXAñUU::=ìBì jì»Cçì h»nï∏„umìbêGer iéë/á"jì»\foêGo"ìAì jì»\c"ì jçìh»the-emptê∏„y-string iéé¶ççë?Œ(defruleë?˝Aéé°ççën?Â:=ñ?˝BíÉ?µ;ì(1)éé°ççën?Â:=ñ?˝(CìNUMBER)ëSˇ–;ì(2)éé°ççën?Â:=ñ?˝("foo"ìA)ëY?Õ;ì(3)éé°ççën?Â:=ñ?˝"c"ëxøª;ì(4)ééë?ü    ˝úâffâˇvü    J=çççë "5ü˝-:∞5ééëL‹ªTheñ’XKleeneì*ìindicatesì0ìorìmoreìoê<rccurencesìofìtheìprecedingìconstituenê√étééüçíÈ»3ééå㵆l熽ª†'熽¸ççën?ÂŒ:=ñ?˝()ë}ˇ∏;ì(5)éé§ ççën?Â)éé©ŒsçëN»Thisñ»ˇruleìdescriböGesì5ìproòductions,ëÂÈallìderivingìtheìnon-terminalìŒA».ìEacê∏„hìofé°çë?theñx·proêGductionsìhasìtheìleft-handìsideìŒA».ìTheìrighê∏„t-handìsideìofì(1)ìconsistsìofé°çë?justñè&oneìconstituenö∏„t,ë∂ theìnon-terminalìŒB».ì(2)ìhasìaìrighòt-handìofìlengthì2,ë∂ andìitsé°çë?secondñÿ/constituenö∏„tìisìtheìnon-terminalìŒNUMBERëÿ»(whicòhìrewritesìtoìanòyìinòteger,é°çë?realñÿoorìrational).õ˚(3)ìisìaìrecursivê∏„eìproêGduction.ò(4)ìconê∏„tainsìjustìtheìterminalé°çë?(orõUUkï∏„eywìord)òŒ"c"».ëq«(5)òderivìesòtheòemptìyòstring.é°çëNNoneñ£≠ofìtheseìproêGductionsìhasìaìsemanö∏„ticìactionìattacòhed.ë\–Byìdefault,ë∑Ctheé°çë?semanö∏„ticñDÎactionìisìtheìŒidentityì»functionìifìtheìrighòt-handìsideìofìtheìruleìcon-é°çë?sistsñïofìaìsingleìconstituenê∏„tìandìtheìŒidentity*ì»functionìotherwise.ë\2(Œidentity*é°çë?»isñUUde nedìasìtheìfunctionìthatìreturnsìallìitsìargumenê∏„tsìasìaìlist.)éüqjçë?ÕGrammarñ4RuleìSemanêÆ9ticìActionsë
  19. »Ifñßßwö∏„eìwòanòtìtoìattacòhìotherìthanìtheseé°çë?defaultñUUsemanö∏„ticìactions,ìwòeìhaòvòeìtoìuseìaìŒ:buildì»clauseìafterìaìproêGduction.é°çëNTheñUUbuildìclauseìhasìtheìsynê∏„tax:é¶çççë? h»buildëUUclause iéë}’]»::=ñUUŒ:buildì»(ç h»lispìfunction iéçëAU_h»argumenê∏„tìlist iéíÉ@»)éé°çççë? h»buildëUUclause iéë}’]»::=ñUUŒ:buildçì h»atomicìlispìform iééé°çççë?h»buildëUUclause iéë}’]»::=ñUUŒ:buildì»(Œ:formçì h»lispìform iéë1Œ@»)éé°çççë? h»buildëUUclause iéë}’]»::=ñUUŒ:buildì»(Œ:typeçì h»struct-tê∏„ypêGe iééé°ççíµ8‹Œ:mapëïR»((ç h»non-terminal iéëC@
  20. ».çëq« h»Slot iéëqû)ëUU...))éé¶çëNTheñUU rstìcaseé©qıçëXŒ:buildñUU»(ç h»lispìfunction iéçëAU_h»argumenê∏„tìlist iéíÉ@»)éüqˆçëNisñ©≈likö∏„eìaìfunctionìcall.ëoItìmaòyìconòtainìfreeìvëˇq«ariableìoêGccurrences.ëoTheseìwillé°çë?bïGeõ¸bìoundòtoòtheònon-terminalòconstituenê∏„tsòofòtheòsameònameòoìccuringòinòtheé°çë?righö∏„t-handñUUsideìofìtheìproêGductionìatìtheìtimeìofìapplyingìtheìsemanòticìaction.é°çëNInñUUtheìsecondìcaseé¶çëXŒ:buildçñUU h»atomicìlispìform iééüqˆçëN»theçëZÈ h»atomicñUUlispìform iéëWıfi»mê∏„ustñZÈböGeìaìfunction.ëÇÇItìwillìbòeìappliedìtoìtheìcon-é°çë?stituenö∏„tsñáofìtheìrighòt-handìside.ë \ThisìfunctionìshouldìhaòvòeìtheìsameìnòumòbêGeré°çë?ofñÊΔargumenö∏„tsìasìtheìrighòt-handìsideìofìtheìcorrespöGondingìproòductionìhasìcon-é°çë?stituenê∏„ts.é°çëNSinceñ=—itìhappêGensìoften,ëBÖthatìonlyìsomeìofìtheìconstituenö∏„tsìofìtheìrighòt-handé°çë?sideñ®Ûareìselected,õΩ⁄orìcomê∏„bined,òaìfewìusefulìsemanö∏„ticìactionsìhaòvòeìbêGeenìprede-é°çë? nedñUUinìœZebu».ççü¸^ˇµ6ééé°çëN»Anñˇexampleìforìsucö∏„hìaìprede nedìactionìisìtheìfunctionìŒcons-2-3ì»whicòhé°çë?takö∏„esñUU3ìargumenòtsìandìreturnsìaìÀcëˇ}'onsì»ofìitsìsecondìandìthirdìargumenòt.é°çëNTheñ[˜thirdìformìofìtheìŒ:buildì»clauseìisìjustìaìlongìwï∏„aìyñ[˜toìwriteìtheì rsté°çë?form,ëUUi.e.éë?ü(âffâˇvü    J=çççë "5ü˝-:∞6ééëL‹ªTheyñ’Xareìdescribê<redìinìtheì leì"zebu-actions.l".ééüçíÈ»4ééåã&◊†l熽ª†'熽¸çëXŒ:buildñUU»(ç h»lispìfunction iéçëAU_h»argumenê∏„tìlist iéíÉ@»)é§çëNisñUUtheìsameìasé°çëXŒ:buildñUU»(Œ:formì»(ç h»lispìfunction iéçëAU_h»argumenê∏„tìlist iéíÉ@»))é°çëNSimilarlyëˇ*™,é§çëXŒ:buildñUU»(prognçì h»atomicìlispìform iéëRïa»)é°çëNisñUUtheìsameìasé°çëXŒ:buildñUU»(Œ:formçì h»atomicìlispìform iéëRïa»)é°çëNTheñUUlastìŒ:buildì»clauseìisìmoreìinê∏„teresting:é§ççëq
  21. Œ:buildñUU»(Œ:typeçì h»struct-tê∏„ypêGe iééé© ççíó∏‹Œ:mapëïR»((ç h»Nonê∏„terminal iéëAï_».çëq« h»Slot iéëqû)ëUU...))éé°çëNwhereçëcã h»struct-tê∏„ypêGe iéë>±»»isñcãaìsymö∏„bêGolìthatìmòustìbêGeìtheìnameìofìaìstructureìtòypêGe.é¶çë?Insteadñ§7ofìhaö∏„vingìtoìwriteìtheìsemanòticìactionìasìaìconstructingìform,ë∑Ôwòeìjusté¶çë?haï∏„vìeñÔÖtoìspöGecifyìtheìtê∏„ypòeìandìtheìmappingìofìnon-terminalsìtoìslots,ëasìinìtheé¶çë?folloê∏„wingëUUexampleççü¸^ˇµ7ééë|s»:é§ççë?Œ(defruleë?˝Boolean-Expréé¶ççën?Â:=ñ?˝(Formula.1ì"and"ìFormula.2)éé¶ççën?Â:buildñ?˝(:typeìBoolean-Andéé¶ççíò?Õ:mapñ?˝((Formula.1ì.ë
  22. ˙:-rand1)éé¶ççí∑øª(Formula.2ë?˝.ë
  23. ˙:-rand2)))é鶶ççën?Â:=ñ?˝(Formula.1ì"or"ìFormula.2)éé¶ççën?Â:buildñ?˝(:typeìBoolean-Oréé¶ççíò?Õ:mapñ?˝((Formula.1ì.ë
  24. ˙:-rand1)éé¶ççí∑øª(Formula.2ë?˝.ë
  25. ˙:-rand2)))éé¶ççën?Â)éé°çëN»TheñºmapìindicatesìthatìtheìslotìŒ-rand1ì»isìtoìbêGeì lledìbê∏„yìtheìvëˇq«alueìofìtheé¶çë?non-terminalñUUŒFormula.1»,ìetc.é¶çëNThisñƒexampleìalsoìmakö∏„esìuseìofìtheìŒ".n"ì»notation:ëP~Ifìonìtheìrighòt-handìsideé¶çë?ofñƒvaìproöGductionìaìnonê∏„terminalìoòccursìrepòeatedlyëˇ*™,ë·owö∏„eìdistinguishìitìbòyìappêGendingé¶çë?Œ"."ñUU»andìaìdigit.é¶çëNTheñÖ“functionìŒprint-actionsì»appliedìtoìtheìnameìofìaìgrammarìmaê∏„yìbêGeé¶çë?usedñ>toì ndìoutìwhatìtheìgeneratedìcoöGdeìforìtheìsemanê∏„ticìactionsìloòoksìlikê∏„e,é¶çë?e.g.ëq«afterñUUcompilingìtheìsampleìgrammarìŒ``pc1.zb''»:éë?üüJâffâˇvü    J=çççë "5ü˝-:∞7ééëL‹ª(takê√éenñ’Xfromìtheìgrammarìnamedì\pö<rc1";ìseeìtheì leì\pòc1.zb"ìinìtheìtestìdirectory)ééüçíÈ»5ééåã3†l熽ª†'熽¸çë?Œ(print-actionsë?˝"pc1")éüçë?...é§ çë?Rule:ë?˝BOOLEAN-EXPRé°çë?(LAMBDAñ?˝(FORMULA.1ìDUMMYìFORMULA.2)é°çëhˇË(DECLAREñ?˝(IGNOREìDUMMY))é°çëhˇË(MAKE-BOOLEAN-ANDñ?˝:-RAND1ìFORMULA.1ì:-RAND2ìFORMULA.2))é°çë?(LAMBDAñ?˝(FORMULA.1ìDUMMYìFORMULA.2)é°çëhˇË(DECLAREñ?˝(IGNOREìDUMMY))é°çëhˇË(MAKE-BOOLEAN-ORñ?˝:-RAND1ìFORMULA.1ì:-RAND2ìFORMULA.2))é°çë?...é©çëN»Theseñ>semanö∏„ticìactionsìhaòvòeìbêGeenìgeneratedìfromìtheìŒ:buildì»clausesìofìtheé°çë?abêGoï∏„vìeñUUruleìforìŒBoolean-Expr».éü!ƒççë?Ê3éëW÷ˇTheñÖOptionsìListìofìtheìGrammarìFileéüÁççë?fl3.1éë]¿Keywï†ordõÄArgumenìtsòtoòGrammaròConstructionéüuTçë?»Someñ|<globalìinformationìtoìconê∏„trolìgrammarìcompilation,õÖˆlexicalìanalysis,òandé°çë?theñDÈgenerationìofìsemanê∏„ticìactionsìwillìböGeìdeclaredìinìtheìbòeginningìofìaìgrammaré°çë? leççü¸^ˇµ8ééë|s».ëj(Wëˇ*™eñ>wcö∏„hoseìtoìletìtheì rstìlistìofìaìgrammarì leìtakòeìtheìformìofìaìkòeywòordé°çë?argumenö∏„tñÀ€listìtoìbêGeìgivòenìtoìtheìfunctionìŒzb:make-grammar».ë’YTheìfolloòwingé°çë?kï∏„eywìordsñUUareìvëˇq«alid:é¶ççë?Œ:nameë{¿-»añUUstring,ìtheìnameìofìtheìgrammaréé°°ççë?Œ:packageël6»añUUstring,ìtheìnameìofìtheìpacê∏„këˇq«ageìwhereìtheéé°ççí’non-terminalñUUsymö∏„bêGolsìandìtheìfunctionìsymòbêGolséé°ççí’usedñUUinìsemanê∏„ticìactionsìresideéé°°ççë?Œ:identifier-start-charsë@c»añUUstring.ëq«Duringìlexicalìanalysisìanê∏„yéé°ççí’cê∏„haracterñUUinìthisìstringìcanìstartìanìŒidentifieréé°ççí’»non-terminal.éé°ççí’TheñUUdefaultìisìŒ*identifier-start-chars*».éé°°ççë?Œ:identifier-continue-charsë
  26. Äl»añUUstring.ëq«Duringìlexicalìanalysisìanê∏„yéé°ççí’cö∏„haracterñUUinìthisìstringìcanìconòtinòueìanéé°ççí’ŒidentifierñUU»(i.e.ëq«cê∏„haractersìnotìinìthisìstringéé°ççí’terminateñUUŒidentifier»).ëq«Theìdefaultìiséé°ççí’Œ*identifier-continue-chars*».éé°ççë?Œ:string-delimiterë<¿Q»añUUcö∏„haracter,ìtheìcòharacterìthatìdelimitsìaééë?ü
  27. âffâˇvü    J=çççë "5ü˝-:∞8ééëL‹ªAñ’Xgrammarì leìhasìtheìdefaultìtê√éypê<reì".zb".ééüçíÈ»6ééåã;?†l熽ª†'熽¸ççí’»stringñUUtoìbêGeìrepresenê∏„tedìasìaìœCommonìLispì»string.éé§ ççí’(defaultëUUŒ#\"»)éé°°ççë?Œ:symbol-delimiterë<¿Q»añUUcö∏„haracter,ìtheìcòharacterìthatìdelimitsìaéé°ççí’stringñUUtoìbêGeìrepresenö∏„tedìasìaìœCommonìLispì»symòbêGol.éé°ççí’(defaultëUUŒ#\'»)éé°°ççë?Œ:domainëq@3»añUUlist,ìrepresenö∏„tingìtheìhierarcòhòyìofìtheìdomain.éé°ççí’SeeñUUsectionìÕ??ëq«»bêGeloê∏„w.éé°°ççë?Œ:domain-fileëWB»añUUstringìnamingìtheì leìwhereìtheìgeneratedìCLéé°ççí’programñUUthatìimplemenê∏„tsìtheìdomainìwillìbêGeìstored.éé°ççí’De nitionsñUUofìfunctionsìforìsemanê∏„ticìactionsìandéé°ççí’regularñUUexpressionìcategoriesìareìkö∏„eptìhereìasìwòell.éé°ççí’ThisñUUstringìdefaultsìtoìtheìconcatenationìofìtheéé°ççí’grammar'sñUU:nameìandì\-domain".éé°°ççë?Œ:grammarël6»añUUstring,ìbê∏„yìdefault:ëq«Œ"null-grammar"»,ìnamingìtheéé°ççí’grammarñUUtoìbêGeìusedìtoìparseìtheìgrammarìde nedéé°ççí’inñUUthisì le.ëq«IfìtheìgrammarìŒ"zebu-mg"ì»isìused,éé°ççí’anñUUunparserìwillìalsoìbêGeìgenerated.éé°°ççë?Œ:lex-catsëf¿9»anñUUassoêGciationìlistìofìterminalìcategoryìnamesìandéé°ççí’regularñUUexpressionsì(seeìsectionìÕ??»)éé°°ççë?Œ:white-spaceëWB»añUUlistìofìcö∏„haractersìeacòhìofìwhicòhìwillìbêGeìignoredéé°ççí’bêGeforeñUUaìtokê∏„en.ëq«(defaultìŒ(#\Spaceë?˝#\NewlineëY?Õ#\Tab)»)éé°ççë?Œ:case-sensitiveëG@K»trueñUUifìtheìcaseìofìkï∏„eywìordsñUUisìsigni canê∏„t,éé°ççí’falseñUUotherwiseì(defaultìÀfalse).ééü˛6ççë?fl3.2éë]¿De ningñÄaìDomainéüuTçë?»Theñ«ÜŒ:domainì»kï∏„eywìordñ«ÜisìusedìtoìspöGecifyìaìtê∏„ypòeìhierarcï∏„hìyëˇ*™.ëBÇThisñ«Üspòeci cationìwillé°çë?expandñJQinö∏„toìŒdefstructì»formsìthatìimplemenòtìthisìhierarcòhòyëˇ*™.ënItìisìalsoìpêGossibleé°çë?toñ|Òwriteìsucö∏„hìstructureìde nitionsìdirectlyìinòtoìtheìgrammarì le.ëËöTheìvëˇq«alueìofé°çë?theñUUŒ:domainì»kï∏„eywìordõUUargumenìtòmìustòbêGeòaòlistòofòtheòfolloìwingòform:éüççëO™Æ(ç h»RoêGotëUUStruct iééé°ççëO™ÆŒ:subtypeçñUU h»StructìDesc iééé°ççëO™ÆŒ:subtypeçñUU h»StructìDesc iééé°ççëO™Æ»...)éé°°çççëO™Æ h»RoêGotëUUStruct iéíé„ö»::=çëUU h»Symê∏„bêGol iééé°éüçíÈ»7ééåãCå†l熽ª†'熽¸çççëO™Æ h»StructëUUDesc iéíç’^»::=çëUU h»Symê∏„bêGol iéë.Òœjéé§ ççíûÄ »(çëUU h»Symê∏„bêGol iéë.ÒœŒ:slotsëUU»(ç h»Slot iéëUZ»...)ñq«)ì jéé°ççíûÄ »(çëUU h»Symê∏„bêGol iéë.ÒœŒ:slotsëUU»(ç h»Slot iéëUZ»...)éé°ççí—UiŒ:subtypeçñUU h»StructìDesc iééé°ççí—UiŒ:subtypeçñUU h»StructìDesc iééé°ççíûÄ »...ëq«)éé°°çççëO™Æ h»Slot iéël»::=çëUU h»Symê∏„bêGol iéë.ÒœjñUU»(çì h»SlotìName iéçë<G$h»FillerìTê∏„ypêGe iéëxq÷»)éé°çççëO™Æ h»FillerëUUTê∏„ypêGe iéíã’`»::=çëUU h»Symê∏„bêGol iééé©çëN»Thisñ7ÕdescriböGesìaìtê∏„ypòeìhierarcï∏„hìyñ7Õwithìroòotìnoòdeçì h»RoòotëUUStruct iéë@d».ë.Aë7ínoòdeìofé°çë?theõ˘ hierarcï∏„hìyòtreeòcanòhaìvìeòcìhildren,ëa¯denotedòbìyòŒ:subtypeò»folloìwìedòbìyòtheé°çë?structureñcÀdescriptionìofìtheìcö∏„hildìnoêGde.ëù*EacòhìnoêGdeìcanìhaòvòeìslots,ëgidescribêGedìasé°çë?añj™listìfolloö∏„wingìŒ:slots».ë±≈Aëj§còhildìnoêGdeìinheritsìtheìslotsìofìitsìparenòtìnoêGde.ë±≈Theé°çë?vëˇq«alueñUUofìaìslotìcanìböGeìtê∏„ypòe-restrictedìtoçì h»FillerìTê∏„ypòe iéë<*≤».é°ççëN h»RoêGotëUUStruct iéíéDˇ»willñahbêGeìimplemenö∏„tedìasìaìstructureìtòypöGeìdirectlyìbòeloê∏„wìtheé°çë?structureñØtö∏„ypêGeìŒkb-domain»,ëäFi.e.ë’(Œkb-domain-pì»x)ìisìÀtrueì»forìanòyìinstanceìxìofìaé°çë?subtê∏„ypöGeñUUofçì h»RoòotìStruct iéë?8Ï».éü˛6çë?ÕExampleñˇcdomainìde nitionë
  28. »TheñXÑgrammarìde nedìinì\pêGc2.zb"ìacceptsìaé°çë?simpleñUUpropêGositionalìcalculusìlanguageìwithìsenö∏„tencesìsucòhìasé¶çëXŒwalks(agent:ë
  29. ˙John)»,é¶çë?whicö∏„hñ`Oyieldsìtheìfolloòwingìabstractìsynòtaxì(prinòtedìoutìusingìtheìœCommonìLispé°çë?»structureëUUprinê∏„ter):é©ççëI˙Œ#S(ATOMIC-WFFñ?˝-PREDICATEìWALKSéé°ççííˇ–-ROLE-ARGUMENT-PAIRSë?˝#S(ROLE-ARGUMENT-PAIRéé°ççíˇà-ROLEë?˝AGENTéé°ççíˇà-ARGUMENTñ?˝JOHN)ì)éé¶çëN»TheñdLtö∏„ypêGesì|ìsucòhìasìŒATOMIC-WFFõdH»andìŒROLE-ARGUMENT-PAIRò»|ìareìde nedé°çë?bö∏„yñUUtheìfolloòwingìdomainìdeclaration:é¶ççë?Œ:domainñ?˝(PCì;;ìPCìisìtheìrootìofìtheìhierarchyéé°ççën?Â:subtypeë?˝(Formulaéé°ççí¢ø«:subtypeñ?˝(Propositional-variableì:slotsì(-name))éé°ççí¢ø«:subtypeë?˝(Boolean-Expréé°ççí—ˇ¨:slotsñ?˝((-rand1ìFormula)éé°ççí˚ˇî(-rand2ë?˝Formula))éé°ççí—ˇ¨:subtypeë?˝Boolean-Oréé°ççí—ˇ¨:subtypeë?˝Boolean-And))éé°ççën?Â:subtypeñ?˝(Boolean-Opì:slotsì(-name))éé°ççën?Â:subtypeë?˝(Atomic-WfféééüçíÈ»8ééåã    L?†l熽ª†'熽¸ççí¢ø«Œ:slotsë?˝(-predicateéé§ ççíÃøØ(-Role-Argument-Pairsë?˝Sequence)))éé°ççën?Â:subtypeñ?˝(Role-Argument-Pairì:slotsì(-Roleì-Argument))éé°ççën?Â)ééü!ƒççë?Ê4éëW÷ˇTheñÖÛPm#ΩRff
  30. cmss10ÎPZebuìÊMetaìGrammaréüÁçë?»Usingñ<theìgrammarì"zebu-mg"ìasìtheìŒ:grammarì»argumenê∏„tìinìtheìoptionsìlisté°çë?indicatesñÕèthatìtheìfolloê∏„wingìgrammarìisìtoìböGeìpreproòcessedìwithìtheìgrammaré°çë?\zebu-mg"ñUUbêGeforeìcompilation.é°çëNTheñπadvëˇq«anö∏„tagesìofìtheìmeta-grammarì(vòersusìtheìdefaultìnòull-grammar)ìareé°çë?añFmoreìconciseìrepresenê∏„tationìofìrules,ëÇ<automaticìgenerationìofìtheìfunctionsé°çë?thatñb‘implemenö∏„tìtheìsemanòticìactionsìandìrevòersibilitòyìofìtheìgrammarì(genera-é°çë?tionñUUofìprinê∏„tingìfunctions).é°çëNTheñ,ódisadvëˇq«anö∏„tageìisìthatìtheìsemanòticsìisìlimitedìtoìconstructingìtòypêGedìfea-é°çë?tureñ{¢structures.ë‰ØButìtheseìhaï∏„vìeñ{¢greatìexpressivö∏„eìpêGoòwòer,ëÖ5andìfurthermoreìcouldé°çë?subsequenö∏„tlyñLÍbêGeìtransformedìinòtoìsomeìotherìprogram.ëXÜTòypêGedìfeatureìstruc-é°çë?turesñ•areìideallyìsuitedìtoìpresenö∏„tìabstractìsynòtax.ëà∑Theìfactìthatìuni cation,é°çë?spöGecializationñandìgeneralizationìareìwê∏„ellìde nedìopòerationsìonìfeatureìstruc-é°çë?tures,ëFÇmakö∏„esñFthemìappropriateìforìfurtherìtransformationsìbòyì(œZebu-RR»).ìFëˇ*™oré°çë?anñUUinö∏„troêGductionìinòtoìfeatureìstructuresìseeì[Õ?»].é°çëNSinceñ‹Òthereìisìaìrestrictedìwï∏„aìyñ‹Òofìexpressingìtheìsemanê∏„ticsìofìaìruleì{ìnamelyé°çë?asñ¯‡aìtê∏„ypöGedìfeatureìstructureì{ìtheìgrammarìcompilerìwillìbòeìableìtoìgenerateé°çë?coöGdeñHcforìtheìdomainìhierarcï∏„hìyñHcandìprinê∏„t-functionsìassoòciatedìwithìeacö∏„hìtòypêGeìofé°çë?thatëUUdomain.é°çëN"zebu-mg"ñUUisìde nedìinìtermsìofìtheìnê∏„ull-grammarìdescriböGedìabòoï∏„vìeççü¸^ˇµ9ééë|s».éü˛6çë?ÕBNFñ’Tdescriptionìofì\zebu-mg":é©çççëX h»Domain-Defn iéíº»::=çëUU h»Tê∏„ypêGe-name iéë?úyŒ":="çëUU h»Fñˇ*™eat-Tìerm iééé°ççíÃ™Δ»[ñUUŒ"<<"ì»"prinö∏„t-function:"ìIdenòti erìŒ">>"ì»]ìŒ";"éé°çççëX h»zb-rule iéíº»::=çëUU h»Non-terminal iéëHá&Œ"-->"çëUU h»Rhs iéëN;Œ";"éé°çççëX h»Rhs iéíº»::=çëUU h»Rhs1 iéçë$N<h»More-Rhs iéëZ#ñjçëUUh»Kleene-Rhs iééé°çççëXh»Rhs1 iéíº»::=çëUU h»Constituenê∏„t iéë>éA»*ñUU[ìŒ" fŒ"çì h»Semanê∏„tics iéë:xŒ" gŒ"ì»]éé°çççëX h»Constituenê∏„t iéíº»::=çëUU h»Idenê∏„ti er iéë5Í∞jçëUUh»String iééé°çççëXh»More-Rhs iéíº»::=ñUU jçìh»Rhs1 iéçë$N<h»More-Rhs iééé°çççëXh»Semanê∏„tics iéíº»::=çëUU h»Fñˇ*™eat-Tìerm iééé°¶çëN»AçëUU h»Fñˇ*™eat-Tìerm iéë;„ì»isñUUaìtê∏„ypêGedìattributeìvëˇq«alueìmatrix.éë?üÊfâffâˇvü    J=çççë "5ü˝-:∞9ééëL‹ªYëˇJ™ouñ
  31. !maö√éyìstudyìtheìde nitionìofìtheìmetaìgrammarìinìtermsìofìtheìnòull-grammarìinìtheéü    Äç leë’X"zebu-mg.zb".ééüçíÈ»9ééåã
  32. U©†l熽ª†'熽¸çççëX h»Fñˇ*™eat-Tìerm iéíº»::=ñUU[ç h»Tê∏„ypêGe-name iéë<G$»":"]çì h»Conj iééé§ çççëXh»Conj iéíº»::=ñUUŒ"["çì h»LabêGel-vëˇq«alue-pair iéëU*∂»*ìŒ"]"éé°çççëX h»LabêGel-vëˇq«alue-pair iéíº»::=ñUUŒ"("çì h»Idenê∏„ti er iéçë5Í∞h»Fñˇ*™eat-Tìerm iéënxÓŒ")"éé°çççëX h»Tê∏„ypêGe-name iéíº»::=çëUU h»Idenê∏„ti er iééé©∂"çëN»ThisñUUBNF-notationìmakê∏„esìuseìoféü∂#ççççëK8‚1.éééëXstarñUU(*)ìforì0ìorìmoreìrepêGetitionsìofìtheìprecedingìconstituenê∏„té§[ççççëK8‚2.éééëXbarñUU( j»)ìforìalternationé°ççççëK8‚3.éééëXbracï∏„kìetsñUU([])ìforìmarkingìtheìenclosedìconstituenê∏„tsìasìoptionalé°ççççëK8‚4.éééëXañUUquotationìsymö∏„bêGolì(")ìforìdelimitingìkòeywòordsé¶çëNTheõ3ΩabêGoï∏„vìeòde nitionòisòsomewhatòoìvìersimpli ed,ë:usinceòitòdoêGesònotòdealòwithé§ çë?theñÍß".n"ìnotationìforçì h»Constituenê∏„t iéë?#ì»:ëúkifìonìtheìrighê∏„t-handìsideìofìaìproêGductioné°çë?añÛ˘non-terminalìoöGccursìrepòeatedlyëˇ*™,ë¢wö∏„eìcanìdistinguishìitìbòyìappêGendingì"."ìandé°çë?añ‘digitìtoìtheìidenö∏„ti er.ë≥ETheìsemanòticsìcanìthenìunamòbiguouslyìreferìtoìthisé°çë?idenê∏„ti er.é°çëNTheñ29semanö∏„ticsìisìdescribêGedìasìaìtòypêGedìfeatureìstructure.ëfNamesìofìvëˇq«ariablesé°çë?oöGccuringñçèinìfeatureìtermìpòositionìcorespòondìtoìconstituenö∏„tìnamesìinìtheìrighòt-é°çë?handñfl»sideìofìtheìrule.ë Theìe ectìofìapplyingìaìruleìisìtoìinstanê∏„tiateìaìfeatureé°çë?structureñ±^ofìtheìtê∏„ypöGeìdescribòedìinìtheìruleìsemanê∏„tics,ë“)substitutingìvëˇq«ariablesìwithé°çë?theirëUUvëˇq«alues.é°çëNIfñÇötheìrelationìbêGetï∏„wìeenõÇösemanìticsòandòsynìtaxòisòone-to-one,ëçÎtheòinìvìerseòofòaé°çë?parser,ñUUaìprinê∏„ter,ìcanìbêGeìgenerated.éü∑3ççë?fl4.1éë]¿DomainëÄDe nitionéüuTçë?»AlthoughñJßitìisìpöGossibleìtoìspòecifyìtheìhierarcï∏„hìyñJßofìdomainìtê∏„ypòesìusingìtheé°çë?Œ:domainõ—è»kï∏„eywìordòasòinòsectionòÕ??»,ë0ùaòmoreòconìvìenoienìtòsynìtaxòisòo eredòbìyé°çë?theñUUmetaìgrammarìruleçì h»Domain-Defn iéëEq—».é°çëNTheñUUtê∏„ypêGeìde nitionéü∂#çëXÀatypõˇ}'eñUU»:=ìÀsupòer»:õq«[(…sçüˇµ1éë|s»)ì...ò(…sçüˇÛ 0eórcmmi7∂néëq~»)];é¶çë?willñˇ=de neìtheìtê∏„ypêGeìÀatypõˇ}'eì»inheritingìfromìÀsupòer»,ëuandìhaê∏„vingìslotsì…sçüˇµ1éë{∞»throughì…sçüˇ∂néëq~».é§c´çëXÀatypëˇ}'eñUU»:=ì[(…sçüˇµ1éë|s»)ì...ëq«(…sçüˇ∂néëq~»)];é°çë?isñ«KasìaböGoï∏„vìeñ«Kbutìde nesìtheìtê∏„ypòeìÀatypëˇ}'eì»asìaìsubtê∏„ypòeìofìtheìtopìtê∏„ypòeìnamedé§ çë?ŒKB-domain».é°çëNAñUUslotìmaö∏„yìbêGeìtòypêGeìrestrictedìasìin:éü∂#çëXÀatypõˇ}'eñUU»:=ìÀsupòer»:ëq«[(…sçüˇµ1éë—»ŒKB-sequence»)];é¶çë?whicö∏„hñë`restrictsì…sçüˇµ1éë
  33. ”»toìbêGeìofìtòypêGeìŒKB-sequence».ë%ÈAnìoptionalìÀprint-functionì»maòyé°çë?bïGeõUUspìeci ed,òasòinééüçíÊˇ10ééåã `ʆl熽ª†'熽¸çëXÀatypõˇ}'eñUU»:=ìÀsupòer»:õq«[(…sçüˇµ1éë|s»)]ìŒ<<ìprint-function:òÀprint-atypëˇ}'eìŒ>>»;é§çë?HereñÆÔwö∏„eìsupplyìforìÀatypëˇ}'eì»itsìoòwnìprinòterìcalledìÀprint-atypëˇ}'eì»andìnoìprinòterìwillé© çë?bêGeñUUgeneratedìforìÀatypëˇ}'e».éü˛6ççë?fl4.2éë]¿ExampleëÄGrammarséüuTçë?ÕExampleñ’TGrammarìforìArithmeticìExpressionsé°çë?Œ(:nameñ?˝"arith-exp"ì:grammarì"zebu-mg")é§çë?;;ñ?˝Domainìdefinitioné°çë?Arith-expñ?˝:=ìKb-domain:ì[];é¶çë?FactorëˇÙ:=ñ?˝Arith-exp:ì[(-value)]ì<<print-function:ìPrint-factor>>;é¶çë?Mult-opëø˜:=ñ?˝Arith-exp:ì[(-arg1)ì(-arg2)];é¶çë?Plus-opëø˜:=ñ?˝Arith-exp:ì[(-arg1)ì(-arg2)];é°çë?;;ë?˝Productionsé°çë?EEñ?˝-->ë
  34. ˙EEì"+"ìTTì{ì+-op:ì[(-arg1ìEE)ì(-arg2ìTT)]ì}é¶çëhˇË|ë
  35. ˙TTë?˝;é°çë?TTñ?˝-->ìTTì"*"ìFëø˜{ì*-op:ì[(-arg1ìTT)ì(-arg2ìF)]ì}é¶çëcøÎ|ñ?˝Fì;é°çë?Fñ?˝-->ë
  36. ˙"("ìEEì")"ë)ˇË{ìfactor:ì[(-valueìEE)]ì}é¶çëcøÎ|ñ?˝IDENTIFIERëÓ{ìfactor:ì[(-valueìIDENTIFIER)]ì}é¶çëcøÎ|ñ?˝NUMBERë4‚{ìfactor:ì[(-valueìNUMBER)]ì}ì;éü çëN»Theñfixsemanö∏„ticsìofìtheì rstìruleìsaòysìthatìanìobëé8jectìofìtòypöGeìŒ+-opì»shouldìbòeé¶çë?createdñCìwithìslotìŒ-arg1ì» lledìwithìtheìvëˇq«alueìofìŒEEëCU»andìŒ-arg2ì» lledìwithìtheé¶çë?vëˇq«alueñUUofìŒTT».éü˛6çë?ÕExampleñ@ÎGrammarìforìPropêQ«ositionalìCalculusë
  37. »Thisñëgrammarìde nesé¶çë?theñ`⁄sameìdomainìasìabêGoï∏„vìeñ`⁄(Õ??»).ë ICompilingìitìgeneratesìaìparserìandìaìgenerator.éü"çë?Œ(:nameë?˝"pc2"é¶çëD?˝:packageë?˝"CL-USER"é¶çëD?˝:grammarë?˝"zebu-mg")é°çë?;;ñ?˝DomainìdefinitionééüçíÊˇ»11ééåã l†l熽ª†'熽¸çë?ŒFormulañ?˝:=ìkb-domain:ì[];é©çëD?˝Propositional-variableñ?˝:=ìFormula:ì[(-name)ì];é§ çëD?˝P-FormulaëI÷:=ñ?˝Formula:ì[(-content)ì];é°çëD?˝Boolean-Exprë9øfl:=ñ?˝Formula:ì[(-rand1ìFormula)ì(-rand2ìFormula)];é°çëSˇÙBoolean-Orë4‚:=ñ?˝Boolean-Expr:ì[];é°çëSˇÙBoolean-Andë/?Â:=ñ?˝Boolean-Expr:ì[];é°çëD?˝Atomic-WffëD?Ÿ:=ñ?˝Formula:ì[(-predicate)é°çí?ë(-Role-Argument-Pairsë?˝RAP-list)];é¶çë?Role-Argument-Pairñ?˝:=ìkb-domain:ì[(-Role)ì(-Argument)];é¶çë?RAP-listñ?˝:=ìkb-domain:ì[(-first)ì(-rest)];é°çëI˙RAP-empty-listñ?˝:=ìRAP-list:[];é¶çë?;;ë?˝Productionsé¶çë?Formulañ?˝-->ìPropositional-variableé°çë}ˇ‹|ë?˝Boolean-Expré°çë}ˇ‹|ñ?˝"("ìFormulaì")"ì{P-Formula:[(-contentìFormula)]}é°çë}ˇ‹|ë?˝Atomic-Wff;é¶çë?Propositional-Variableé°çëI˙-->ñ?˝Identifierì{Propositional-variable:ì[(-nameìIdentifier)]};é¶çë?Boolean-Exprñ?˝-->ìFormula.1ì"and"ìFormula.2é°çíò?Õ{Boolean-And:ñ?˝[(-rand1ìFormula.1)é°çíÊˇ†(-rand2ë?˝Formula.2)]}é¶çííˇ–|ñ?˝Formula.1ì"or"ìFormula.2é°çíù {Boolean-Or:ñ?˝[(-rand1ìFormula.1)é°çíÊˇ†(-rand2ë?˝Formula.2)]};é¶çë?Atomic-Wffñ?˝-->ìIdentifierì"("ìRole-Argument-Pairsì")"é°çíçø”{ë?˝Atomic-Wff:é°çíò?Õ[(-predicateë?˝Identifier)é°çíù (-Role-Argument-Pairsë?˝Role-Argument-Pairs)]};é¶çë?Role-Argument-Pairsë?˝-->é°çë^Ó{ñ?˝RAP-empty-list:ì[]ì}é°çë^Ó|ñ?˝Role-Argument-PairìRole-Argument-Pairsé°çëhˇË{ñ?˝RAP-list:ì[(-firstìRole-Argument-Pair)é°çí≠?¡(-restë
  38. ˙Role-Argument-Pairs)]};ééüçíÊˇ»12ééåã
  39. rX†l熽ª†'熽¸çë?ŒRole-Argument-Pairë?˝-->é§ çë^ÓIdentifierñ?˝":"ìTermé°çë^Ó{Role-Argument-Pair:ñ?˝[(-RoleìIdentifier)é°çí—ˇ¨(-Argumentë?˝Term)]};éüçë?Termñ?˝-->ë
  40. ˙Identifierì|ìNumberì;é°ü˙gççë?fl4.3éë]¿TheñÄKleeneì*ìNotationéüuTçë?»Theñfimeta-grammarì\zebu-mg"ìproê∏„videsìanìabbreviatedìnotationìforìrepêGeatedé°çë?oêGccurrencesñUUofìaìnon-terminal,ìseparatedìbö∏„yìaìkòeywòord.ëq«Theìsynòtaxìforìthisìis:é©ȉçççë`U\ h»Kleene-Rhs iéí´Uk»::=çëUU h»Idenê∏„ti er iéë5Í∞Œ*çëUU h»String iéíòÄ(»(1)éé°çççë`U\ h»Kleene-Rhs iéí´Uk»::=çëUU h»Idenê∏„ti er iéë5Í∞Œ+çëUU h»String iéíòÄ(»(2)éé°¶çëNTheñp¨meaningìofì(1)ìisìthatì0ìorìmoreìoêGccurrencesìofìtheìconstituenê∏„tìnamedé°çë?bï∏„yçë’ú h»Idenìti er iéë8Î>»andñ’úseparatedìbö∏„yçì h»String iéë,$"»willìbêGeìacceptedìbòyìthisìrule,ë5Æandé°çë?thatñB-theìsequenceìofìtheìresultsìofìtheseìconstituenê∏„tsìwillìbêGeìreturnedìasìtheé°çë?semanê∏„ticsñÌïofçì h»Kleene-Rhs iéë<XE».ëO2Theìmeaningìofì(2)ìisìtheìsame,ëVexceptìthatìatìleasté°çë?oneñUUoöGccurrenceìofìtheìconstituenê∏„tìhasìtoìbòeìfound.é°çëNTheñësemanê∏„ticsìofìaçì h»Kleene-Rhs iéëBåûproêGductionìisìanìimplicitìsequenceìcon-é°çë?struction.ëoœTheñˇXKleene-constituenö∏„tì(ç h»Idenòti er iéë3?^»concatetenatedìwithìŒ*ì»orìŒ+»)ìisé°çë?böGoundñUUinìtheìsemanê∏„ticsìofìtheìproòduction,ìe.g.é¶çë?ŒDisjunctionñ?˝-->ìConjunction+ì"|"é°çííˇ–{Disj:ñ?˝[(-termsìConjunction+)]};é°¶çëN»buildsñ‰íaìstructureìofìtö∏„ypêGeìŒDisjì»withìtheìŒ-termsì»slotì lledìbòyìtheìvëˇq«alueìofé°çë?theñUUKleene-constituenê∏„tìŒConjunction+».éü˙gçë?ÕExampleñ’TgrammarìusingìKleeneì*ìNotationéüÓPçë?Œ(:nameñ?˝"mini-la"ì:grammarì"zebu-mg"ì)é§çë?;;ñ?˝Domainìdefinitioné°çë?Programñ?˝:=ì[(-stmtsìkb-sequence)];éü çë?Applicationñ?˝:=ì[(-function)ì(-argsìkb-sequence)];é°çë?;;ë?˝rulesééüçíÊˇ»13ééåãx^†l熽ª†'熽¸çë?ŒProgramñ?˝-->ì"begin"ìStmt+ì";"ì"end"é© çíÉ?Ÿ{ñ?˝Program:ì[(-stmtsìStmt+)]ì}ì;é§çë?StmtëˇÙ-->ñ?˝Identifierì|ìApplì|ìProgramì;é°çë?ApplëˇÙ-->ñ?˝Identifierì"("ìArg*ì"ì"ì")"é¶çíÉ?Ÿ{Application:ñ?˝[(-functionìIdentifier)ì(-argsìArg*)]};é°çë?Argë?Ò-->ñ?˝Identifierì|ìNumberì|ìApplì;é¶üçëN»CompilingñOWthisìgrammarìgeneratesìaìparser/unparserì(i.e.ëo»theìprinê∏„tingìrou-é¶çë?tinesñUUareìgeneratedìautomatically).é§çë?Œ(zb:read-parserñ?˝"beginìA;ìBì;ìCìend"é¶çííˇ–:grammarñ?˝(zb:find-grammarì"mini-la"))鶰çëN»returnsñ·aìstructureìofìtö∏„ypêGeìŒPROGRAMë—»whicòhìisìprinòtedìinìtheìsynòtaxìofì\mini-é¶çë?la":é°çë?Œbeginñ?˝A;B;Cìendé¶çë?>ñ?˝(describeì*)é¶çë?beginñ?˝A;B;CìendìisìaìstructureìofìtypeìPROGRAM.é¶çë?Itñ?˝hasì1ìslot,ìwithìtheìfollowingìvalues:é¶çëD?˝-STMTS:ësæA;B;Céüçë?(describeñ?˝(PROGRAM--STMTSì*))é¶çë?A;B;Cñ?˝isìaìstructureìofìtypeìKB-SEQUENCE.é¶çë?Itñ?˝hasì2ìslots,ìwithìtheìfollowingìvalues:é¶çëD?˝FIRST:ëxøªAé¶çëD?˝REST:ë}ˇ∏Bë?˝Cé¶ü!ƒççë?Ê5éëW÷ˇUsingñÖtheìCompileréüÁççë?fl5.1éë]¿CompilingñÄaìgrammaréüuTçë?»TheñUUœZebu»-compilerççü¸^ˇµ10ééë Œ;»canìbêGeìcalledìusingìanö∏„yìofìtheìfolloòwingìfunctions:é°ççë?Œzebu-compile-fileí€ΔÀfunctionéé¶ççíÅ™∏»(Àgrõˇ}'ammar- leñUUŒ&keyìÀoutput- leìgròammarìverbòose»)ééë?ü
  41. âffâˇvü    J=çççëwéü˝-:∞10ééëL‹ªFëˇJ™orñ’Xinstallationìseeìappê<rendixìÎN??ª.ééüçíÊˇ»14ééåã†l熽ª†'熽¸çëN»ThisñêÚcompilesìtheìLALR(1)ìgrammarìinìaì leìnamedìÀgrëˇ}'ammar- le».ë$ûTheé§ çë?Àoutput- leñ™»»defaultsìtoìaì leìwithìtheìsameìnameìasìÀgrëˇ}'ammar- leì»butìtê∏„ypêGeì"Œtab»".é°çë?Theñ®xgrammarìusedìforìcompilationìdefaultsìtoìtheìnê∏„ull-grammar.ëk1IfìÀverbëˇ}'oseì»isé°çë?Àtrue»,ëÚlcon
  42. ictñ”wö∏„arningsìwillìbêGeìprinòted.ëÍÃŒzebu-compile-fileì»returnsìtheìpath-é°çë?nameñUUofìÀoutput- le».éü˛6çë?ÕExample:éüçëD?˝Œ(letñ?˝((*warn-conflicts*ìt)é°çëcøÎ(*allow-conflicts*ë?˝t))é°çëNø˜(zebu-compile-fileë?˝"dangelse.zb"é°çí≤æ:output-fileë?˝"/tmp/dangelse.tab"))é©çëD?˝;ñ?˝ZebuìCompilingì(Versionì2.0)é°çëD?˝;ñ?˝"~/zebu/test/dangelse.zb"ìtoì"/tmp/dangelse.tab"é¶çëD?˝Readingñ?˝grammarìfromìdangelse.zbé¶çëD?˝Startñ?˝symbolsìis:ìSé¶çëD?˝4ñ?˝productions,ì8ìsymbolsé°çëD?˝.........9ñ?˝itemìsetsé°çëD?˝.........é°çëD?˝.........é°çëD?˝;;;ñ?˝Warning:ìACTIONìCONFLICT!!!--ìstate:ì8é°çëD?˝;;;ë4‚oldñ?˝entry:ì(6ì:Sì2)ë
  43. ˙newìentry:ì(6ì:Rì2)é°çëD?˝;;;é°çëD?˝;;;ñ?˝Warning:ìContinuingìtoìbuildìtablesìdespiteìconflicts...é°çëD?˝;;;ë4‚Willñ?˝preferìoldìentry:ì(6ì:Sì2)é¶çëD?˝Dumpingñ?˝parseìtablesìtoì/tmp/dangelse.tabé°çëD?˝#P"/tmp/dangelse.tab"é§ççë?*warn-conflicts*í‡U√Àvariableéé°çëN»Ifñ·Àtrueì»duringìLALR-tableìconstruction,ëDshift-reduceìcon
  44. ictsìwillìbêGeìre-é© çë?pêGorted.ëq«ByñUUdefault,ìŒ*warn-conflicts*ì»isìfalse.é°ççë?Œ*allow-conflicts*í€ΔÀvariableéé°çëN»IfñLÎÀtrueì»duringìLALR-tableìconstruction,ëÅÕshift-reduceìcon
  45. ictsìwillìbêGeìresolvê∏„edé¶çë?inõUUfaï∏„vìoròofòtheòoldòenìtryëˇ*™.ëq«Byòdefault,òŒ*allow-conflicts*ò»isòÀtrue».é°ççë?Œ*check-actions*íÂï¿ÀvariableéééüçíÊˇ»15ééåãÖ«†l熽ª†'熽¸çëN»IfñπÀtrueì»theìsemanê∏„ticìactionìassoöGciatedìwithìaìproòductionìwillìbòeìcompiledìaté§ çë?grammarñ‚[compilationìtimeìinìorderìtoìdisplaö∏„yìpêGossibleìwòarningìmessages.ëŸByé°çë?default,ñUUŒ*check-actions*ì»isìfalse.é§ççë?(Œcompile-slr-grammarñUU»(Àgrõˇ}'ammar- leìŒ&keyìÀoutput- leìgròammar»)ë=Àfunctionéé°çëN»ThisñUUisìlikê∏„eìŒzebu-compile-file»,ìbutìanìSLR-tableìwillìbêGeìmade.é§ çëNExample:éüçëD?˝Œ(compile-slr-grammarë?˝"dangelse.zb"é°çëY?Ò:output-fileë?˝"/tmp/dangelse.tab")é§çëD?˝Readingñ?˝grammarìfromìdangelse.zbé°çëD?˝Startñ?˝symbolsìis:ìSé°çëD?˝4ñ?˝productions,ì8ìsymbolsé© çëD?˝.........9ñ?˝itemìsetsé°çëD?˝Dumpingñ?˝parseìtablesìtoì/tmp/dangelse.tabé¶çëD?˝#P"/tmp/dangelse.tab"鶧ççë?compile-lalr1-grammarñUU»(Àgrõˇ}'ammar- leìŒ&keyìÀoutput- leìgròammar»)ëv“Àfunctionéé°çëN»ThisñUUisìlikê∏„eìŒzebu-compile-file»,ìbutìdoêGesìnotìexpandìlogicalìpathnames.é¶çëNExample:é°çëD?˝Œ(compile-lalr1-grammarë?˝"dangelse.zb"é¶çíºˇ∏:output-fileë?˝"/tmp/dangelse.tab")é§çëD?˝Readingñ?˝grammarìfromìdangelse.zbé°çëD?˝Startñ?˝symbolsìis:ìSé°çëD?˝4ñ?˝productions,ì8ìsymbolsé¶çëD?˝.........9ñ?˝itemìsetsé¶çëD?˝.........é¶çëD?˝.........é¶çëD?˝Dumpingñ?˝parseìtablesìtoì/tmp/dangelse.tabé¶çëD?˝#P"/tmp/dangelse.tab"éü˛6ççë?fl5.2éë]¿LoadingñÄaìgrammaréüuTççë?Œzebu-load-fileñUU»(À lenameìŒ&keyìÀverbëˇ}'ose»)íÄvûÀfunctionéééüçíÊˇ»16ééåãåó†l熽ª†'熽¸çëNÀ lenameñ®L»shouldìböGeìtheìnameìofìaìcompiledìgrammarì le,ëΩ
  46. i.e.ëj¨aì leìofìtê∏„ypòeé§ çë?"Œtab»".ë!Ifñ8ssucê∏„hìaì leìcanìböGeìfound,ëq:itìwillìbòeìloaded,ëq:returningìtheìgrammaré°çë?obëé8jectñLneededìforìparsing.ëUŸInìcaseìaìdomain- leìwö∏„asìgeneratedìbòyìcompilingé°çë?theña±grammar,ëd»itìwillìalsoìböGeìloaded.ëñ⁄Theìtê∏„ypòeìofìtheìdomain- leìisìtheì rstìforé°çë?whicö∏„hñUUaì leìexists,ìbòyìexaminingìtheìlistsé©çëXŒ*load-binary-pathname-types*ëUU»andé°çëXŒ*load-source-pathname-types*é¶çë?»inëUUturn.é°çëNTheõUUkï∏„eywìordòargumenìtòÀverbëˇ}'oseò»defaultsòtoòÀtrue».éü˛6çë?ÕExample:é¶çëD?˝Œ(zebu-load-fileë?˝"/tmp/dangelse.tab")é°çëD?˝<Zebuñ?˝Grammar:ìdangelse>é¶çëN»ItñXTisìpêGossibleìtoìhaï∏„vìeõXTmanìyògrammarsòloadedòconcurrenìtlyëˇ*™.ëz≈Givìenòtheònameé°çë?ofñUUaìgrammar,ìoneìcanì ndìaìgrammarìthatìhasìbêGeenìloadedìbê∏„y:é§ççë?Œfind-grammarëUU»(Àname»)í“∂uÀfunctionéé°çëNnameñYò»mê∏„ustìbêGeìaìstring.ë~èIfìaìgrammarìofìtheìsameìnameì(ignoringìcase)ìhasé§ çë?bêGeenñUUloaded,ìtheìgrammarìobëé8jectìisìreturned,ìelseìÀfalseì»isìreturned.éü˛6çë?ÕExample:é¶çëD?˝Œ(find-grammarë?˝"dangelse")é°çëD?˝<Zebuñ?˝Grammar:ìdangelse>é°ü˛6ççë?fl5.3éë]¿Pê†arsingñÄaìstringìwithìaìgrammaréüuTççë?Œread-parserí˙ï¥Àfunctionéé°ççíÅ™∏»(ÀstringñUUŒ&keyìÀgrõˇ}'ammarìjunk-alëÇÿloweòdìprint-pòarse-erròorsìerròor-fnìstart»)éé©çëNTheñ›\argumenö∏„tìofìtheìŒ:grammarì»kòeywòordìdefaultsìtoìŒ*current-grammar*é°çë?»initiallyñUUisìbêGoundìtoìtheìnê∏„ull-grammar,ìe.g.é¶ççëO™ÆŒ(read-parserçë?˝ hÀstring iéë+1∑Œ:grammarñ?˝(find-grammarçì hÀname iéë$âÍŒ))éé°°ççëO™Æ»isñUUequivëˇq«alenê∏„tìtoéé°°ççëO™ÆŒ(setqñ?˝zebu:*current-grammar*ì(find-grammarçì hŒname iéë"Œ))éé°ççëO™Æ(read-parserçë?˝ hŒstring iéë,á    Œ)éééüçíÊˇ»17ééåãíg†l熽ª†'熽¸çëNŒread-parserñI˜»parsesìtheìstringìstartingìatìtheìpêGositionìindicatedìbê∏„yìŒ:starté§ çë?»(defaultëUU0).é°çëNŒread-parserñìB»takö∏„esìtheìkòeywòordìargumenòtìŒ:junk-allowed»,ë∫whicòhìifìÀtrueì»willé°çë?returnñ{asìsecondìvëˇq«alueìanìindexìtoìtheìunparsedìremainderìofìtheìstringìinìcaseé°çë?notñUUtheìenö∏„tireìstringìwòasìconsumedìbòyìtheìparse.é°çëNTheõJYkï∏„eywìordòŒ:junk-allowedò»hasòtheòsameòmeaningòasòinòtheòœCommonòLispé°çë?»functionëUUŒread-from-string».é°çëNŒ:print-parse-errorsñæ<»conö∏„trolsìtheìprinòtingìofìerrorsìduringìparsingìandé°çë?defaultsñUUtoìÀtrue».é°çëNŒ:error-fnñ6ë»isìaìfunctionìusedìtoìrepêGortìerrors,ënflitìdefaultsìtoìtheìœCommoné°çë?LispñUUŒerrorì»function.éü˛6çë?ÕExample:é©çëD?˝Œ(read-parserñ?˝"ifìfìthenìifìgìthenìhìelseìi"é°çíà÷:grammarñ?˝(find-grammarì"dangelse"))é°çëD?˝("if"ñ?˝Fì"then"ì("if"ìGì"then"ìHì"else"ìI))éüçëD?˝(read-parserñ?˝"1ì+ìa"ì:grammarì(find-grammarì"ex1"))é°çëD?˝(+OPñ?˝(EXPRESSIONì(TERMì(FACTORì1)))é°çë^Ó(TERMñ?˝(FACTORìA)))éü˛6ççë?fl5.4éë]¿Pê†arsingñÄfromìaì leìwithìaìgrammaréüuTççë?Œfile-parserñUU»(À leìŒ&keyìÀgrõˇ}'ammarìprint-pòarse-erròorsìverbòose»)ë,ËåÀfunctionééüçëNŒfile-parserñÇØ»parsesìexpressionsìusingìtheìgrammarìspêGeci edìbê∏„yìŒ:grammar»,é°çë?readingñ1vfromìÀ le».õ*Itìreturnsìaìlistìofìtheìparse-results,ëh~i.e.òwhatìwö∏„ouldìhaòvòeé°çë?bêGeenñUUreturnedìbê∏„yìŒread-parser».é°çëNTheñÓ£Œ:grammarì»argumenö∏„tìdefaultsìtoìŒ*current-grammar*ì»{ìwhicòhìinitiallyìisé°çë?bêGoundñUUtoìtheì\nê∏„ull-grammar".é°çëNŒ:print-parse-errorsñæ<»conö∏„trolsìtheìprinòtingìofìerrorsìduringìparsingìandé°çë?defaultsñUUtoìÀtrue».é°çëNŒ:verboseñÉu»conö∏„trolsìwhetherìprinòtingìofìparse-resultsìoêGccurs,ëé¸andìdefaultsìtoé°çë?Àtrue».é°çëNTheñ•proêGcessingìofìcommenö∏„tsìbòyìŒfile-parserì»canìbêGeìin
  47. uencedìbòyìtheìfol-é°çë?loê∏„wingëUUvëˇq«ariables:é¶ççççëMˇˇ éééëXŒzb:*comment-brackets*ñD˛»isìaìlistìofìbracï∏„kìetõD˛pairs.ë@√EvìerythingòbêGetìwìeené°çëXanö∏„yñofìbracòkòetìpairsìisìignored.ëCFInitiallyìŒzb:*comment-brackets*ì»isìseté°çëXtoëUUŒ(("#\|"ñ?˝.ì"|#"))».é¶ççççëMˇˇ éééëXŒzb:*comment-start*ñ÷7»Aë÷lineìbêGeginningìwithìthisìcê∏„haracterìisìignored.ëGhIni-é°çëXtiallyñUUŒzb:*comment-start*ì»isìsetìtoìtheìsemicolonìcê∏„haracter:ëq«Œ#\;ééüçíÊˇ»18ééåãô—†l熽ª†'熽¸çë?ÕExample:é©çëD?˝Œ(zb:file-parserñ?˝"sample-ex1"ì:grammarì(zb:find-grammarì"ex1"))é§ çëD?˝...éü˛6ççë?fl5.5éë]¿Pö†arsingñÄfromìaìlistìofìtokòenséüuTççë?Œlist-parserñUU»(Àtoken-listìŒ&keyìÀgrõˇ}'ammarìjunk-alëÇÿloweòd»)ëKï˚ÀfunctionééüçëNŒlist-parserñ§»isìlikö∏„eìŒread-parserì»exceptìthatìtheìtokòensìthatìareìpassedìbòyé°çë?theñ«ˆscannerìtoìtheìdrivö∏„erìareìalreadyìgivòenìasìtheìelemenòtsìofìÀtoken-list».ë…™Thisé°çë?functionñ±√isìusefulìifìtheìoptionsìforìconö∏„trollingìlexicalìanalysisìgivòenìinìsectioné°çë?Õ??ëq«»areëUUinsucienê∏„t.éü˛6çë?ÕExample:é¶çëD?˝Œ(letñ?˝((*current-grammar*ì(find-grammarì"ex1")))é°çëSˇÙ(list-parserñ?˝'(1ì"+"ìxì"*"ìy)))é°çëD?˝(+OPñ?˝(EXPRESSIONì(TERMì(FACTORì1)))é°çë^Ó(*-OPñ?˝(TERMì(FACTORìX))ì(FACTORìY)))é°ü!ƒççë?Ê6éëW÷ˇLexicalëÖAnalysiséüÁççë?fl6.1éë]¿CustomizationñÄandìRegularìExpressionséüuTçë?»ItñhÏshouldìonlyìseldomlyìbêGeìnecessaryìtoìwriteìaìlexicalìanalyser.ë"˙Beforeìyê∏„ouìwriteé°çë?yï∏„ourõçÉoìwnòlexicalòanalyzer,ëõècìhecìkòwhetheròtheòfolloìwingòvëˇq«ariablesòandòkìeywìordsé°çë?wê∏„ouldñUUsuceìtoìparameterizeìlexicalìanalysis:éüççëSˇÙŒzb:*comment-start*éé°ççëSˇÙzb:*comment-brackets*éé°ççëSˇÙzb:*disallow-packages*éé°ççëSˇÙzb:*preserve-case*éé°ççëSˇÙzb:*case-sensitive*éé°ççëSˇÙ:case-sensitiveéé°ççëSˇÙ:identifier-start-charséé°ççëSˇÙ:identifier-continue-charséé°ççëSˇÙ:string-delimiteréé°ççëSˇÙ:symbol-delimiteréé°ççëSˇÙ:white-spaceéé°ççëSˇÙ:lex-catséé°éüçíÊˇ»19ééåã£X†l熽ª†'熽¸ççë?fl6.2éë]¿Inö†troê`ducingñÄnewìCategoriesìbòyìRegularìExpressionséüuTçë?»TheõUUkï∏„eywìordòŒ:lex-catsò»takìesòasòargumenìtòanòassoêGciationòlistòofòtheòform:é§cççëSˇÙŒ((ç hŒCategory iéçë7hŒRegularë?˝Expression iéíùMÎŒ)ë?˝...)éé°ççëN h»Category iéíÄ“˘»isñK’aìsymê∏„bêGolìnamingìaìlexicalìcategoryìandçì h»RegularëUUExpression iéé§ çë?»isñIaìstringìrepresenê∏„tingìaìregularìexpressionìasìde nedìinìtheìGNUë÷Emacsé°çë?LispñpManö∏„ualì[Õ?»].ë√ETheìregularìexpressionìwillìbêGeìcompiledìinòtoìaìCommonìLispé°çë?functionñR,andìinï∏„vìokìedõR,bìyòŒread-parserò»bêGeforeòtheòbuilt-inòcategoriesò(Idenìti er,é°çë?String,ë}äNumê∏„böGer)ñuareìexamined.ë“FTheìcategoriesìcanìbòeìusedìinìrulesìlikö∏„eìanòyìofé°çë?theñUUbuilt-inìcategories.é°çëNTheñUUregularìexpressionìcompilerççü¸^ˇµ11ééë Œ;»handlesìtheìfolloê∏„wingìconstructs:éü¸_çççë?Õ.ééëG1Δ»Pï∏„erioêGdõUUmatcìhesòanìyòsingleòcìharacteròexceptòaònewline.é§1¿çççë?Õ*ééëIø˛»repöGeatsñUUprecedingìregularìexpressionìasìmanê∏„yìtimesìasìpòossible.é°çççë?Õ+ééëLÒƒ»likö∏„eñUU*ìbutìmòustìmatcòhìatìleastìonce.é°çççë?Õ?ééëIn7»likö∏„eñUU*ìbutìmòustìmatcòhìonceìorìnotìatìall.é°çççë?Õ[çç».ñ™®.ì.ééë
  48. UOÕ]ééëW∏€»'['ñUUbêGeginsìaìcö∏„haracterìset,ìwhicòhìisìterminatedìbòyì']'.é© çëXCharacterñUUrangesìcanìbêGeìindicated,ìe.g.ëq«a-z,ì0-9.é°çççë?Õ[ççëUT»^ééççë™®.ñ™®.ì.ééëˇ˜Õ]ééë_cÉ»formsñUUtheìcomplemenö∏„tìcòharacterìset.é°çççë?Õ$ééëIø˛»matcê∏„hesñUUonlyìatìtheìendìofìaìline.é°çççë? nÕ(...ëp nÕ)ééëe£à»isñUUaìgroupingìconstruct.é°çççë? nçë’ThÕdigit iéééëkúk»means:ë|¥acceptñZÃtheìsameìstringìasìwö∏„asìmatcòhedìbòyìtheìgroupìinìpêGosi-é¶çëXtionçëUU h»digit iéëw».éü•içë?ÕExample:é§cçëD?˝Œ:lex-catsñ?˝((BibTeX-in-bracesì"{[^\\n}]*}"))鶰çëN»de nesñ taìnewìcategoryìŒBibTeX-in-bracesì»whicö∏„hìmatcòhesìanòythingìstartingé¶çë?withñUU\ f»",ìendingìinì\ g»",ìandìnotìconê∏„tainingìeitherìaìnewlineìorì\ g»".駸_çëD?˝Œ:lex-catsñ?˝((Ratio_Numberì"-?[0-9]+/[0-9]+")é¶çëSˇÙ(Simple_Floatë?˝"-?[0-9]*\\.[0-9]+"))鶰çëN»de nesñ«•theìsynö∏„taxìforìrationalsìandì
  49. oatingìpêGoinòtìnòumòbêGers.ë»∑Noteìthatìtheé¶çë?pïGerioìdñ7pneedsìtoìböGeìescapòed,ë=jsinceìitìisìaìspòecialìcê∏„haracterìofìtheìregularìexpres-é¶çë?sionëUUlanguage.éë?üâÌâffâˇvü    J=çççëwéü˝-:∞11ééëL‹ªThanksñ¶toìLaê√éwrenceìE.ìFëˇJ™reilìwhoìwroteìtheìmainìpartìofìtheìRegularìExpressionìCompiler.ééüçíÊˇ»20ééåã©w†l熽ª†'熽¸ççë?fl6.3éë]¿TheñÄfunctionalìinê†terfaceìtoìtheìparsingìengineéüuTçë?»InñÑ@caseìtheìabêGoï∏„vìeñÑ@parameterizationìfacilitiesìforìlexicalìanalysisìareìinsucienê∏„té§ çë?orñw´yö∏„ouìwòanòtìtoìuseìanìexistingìlexicalìanalyzer,ë¿@yòouìneedìtoìunderstandìtheé°çë?functionalñUUinö∏„terfaceìtoìtheìparsingìengineìasìimplemenòtedìbòyìtheìŒlr-parse».é©ÿ‰ççë?Œlr-parseí
  50. U´Àfunctionéé°ççëO™Æ»(Ànext-sym-fnñUUerrõˇ}'or-fnìgròammarìŒ&optionalìÀjunk-alëÇÿloweòdìlast-pòos-fn»)éé¶çëNŒlr-parseñcn»returnsìtheìresultìofìparsingìtheìtokö∏„enìstreamìproêGducedìbòyìÀerrëˇ}'or-fné°çë?»withñ◊9Àgrõˇ}'ammarì»bê∏„yìtheìLALR(1)ìmethoêGd.ëGæInìcaseìÀjunk-alëÇÿloweòdì»isìÀtrueì»itìproêGducesé°çë?asñ0¨secondìvëˇq«alueìaìhandleìtoìtheìyö∏„etìunconsumedìtokòenìstreamìbòyìcallingìtheé°çë?functionëUUÀlast-pëˇ}'os-fn».é°çëNÀnext-sym-fnñ\À»shouldìböGeìbòoundìtoìaìgeneratorìfunctionì|ìaìfunctionìofìnoé°çë?argumenê∏„tsñ˜u|ìthatìwillìböGeìcalledìtoìproòduceìtheìnextìtokê∏„en.ëX&Itìshouldìreturné°çë?tï∏„wìoñI4vëˇq«alues:ëk∑(1)ìtheìtokö∏„enìfoundìandì(2)ìtheìcategoryìofìtheìtokòenì(obtainedìbòyé°çë?theñUUfunctionìŒcategorize».é°çëNÀerrõˇ}'or-fnñÖfi»isìtheìfunctionìtoìbêGeìcalledìinìcaseìofìanìerror.ëcÀgròammarì»isìtheé°çë?grammarñ«‹obëé8jectìthatìconö∏„tainsìimpêGortanòtìinformationìforìlexicalìanalysis,ë‰}(e.g.é°çë?theñUUtableìofìkï∏„eywìords).é°çëNTëˇ*™oñdunderstandìtheìinö∏„terfaceìtoìŒlr-parse»,ë=ÁconsiderìhoòwìŒlist-parserì»(de-é°çë?scribïGedõUUabìoï∏„vìe)òmighìtòhaìvìeòbêGeenòde ned:é¶çë?Œ(defunñ?˝list-parserì(token-listì&keyì(grammarì*current-grammar*)é°çí˚ˇîjunk-allowed)é°çëI˙(letñ?˝((last-positionìtoken-list)é°çëhˇËtoken1)é°çëSˇÙ(check-typeñ?˝token-listìlist)é°çëSˇÙ(lr-parseé°çëY?Ò;;ñ?˝TheìLEXERìsuppliedìtoìtheìparsingìengine:é°çëY?Ò#'(lambdaë?˝()é°çën?Â(ifñ?˝(nullìtoken-list)é°çíÉ?Ÿ(end-of-tokens-categoryë?˝grammar)é°çëxøfl(progné°çíÉ?Ÿ(setqñ?˝last-positionìtoken-listé°çí¢ø«token1ñ?˝(popìtoken-list))é°çíÉ?Ÿ(categorizeñ?˝token1ìgrammar))))é°çëY?Ò;;ñ?˝Theìerrorìfunctionìsuppliedìtoìtheìparsingìengine:é°çëY?Ò#'(lambdaë?˝(string)é°çën?Â(errorñ?˝"~S~%ìRemainingìtokens:ì~S~{ì~S~}"é°çííˇ–stringñ?˝token1ìtoken-list))é°çëY?Ògrammaré°çëY?Òjunk-allowedé°çëY?Ò;;ñ?˝Functionìthatìreturnsìtheìremainingìunparsedìtoken-listé°çëY?Ò#'(lambdañ?˝()ìlast-position))))ééüçíÊˇ»21ééåã≥O†l熽ª†'熽¸§ççë?Œend-of-tokens-categoryëUU»(Àgrëˇ}'ammar»)íéü⁄Àfunctionéé°çëNŒend-of-tokens-categoryñ?ô»returnsìtï∏„wìoñ?ôvëˇq«alues:ëfÈaìtokê∏„enìsignifyingìtheìendìofé© çë?theñUUtokê∏„enìstreamìandìtheìappropriateìlexicalìcategoryëˇ*™.é°ççë?ŒcategorizeñUU»(Àtokenìgrëˇ}'ammar»)í≥    Àfunctionéé°çë?ŒcategorizeñfG»returnsìtheìÀtokenì»itselfìandìitsìcategoryëˇ*™,ëjÑaìnï∏„umìbêGerñfGthatìrepresenê∏„tsé¶çë?oneñ˝ØofìŒnumber»,ñ6Œidentifier»,ìŒstringñ˝Ø»orìaìparticularìterminalìtokê∏„enìofìtheìgram-é¶çë?mar.éü!ƒççë?Ê7éëW÷ˇFñ˛û∏utureëÖWìorkéüÁçë?»Tëˇ*™ranslationõUUinï∏„vìolvìesòthreeòproêGcesses:é§ççççëMˇˇ éééëX»parsingé°ççççëMˇˇ éééëX»transformationé°ççççëMˇˇ éééëX»generationé°çëNœZebuñ<Ú»isìaìtoêGolìthatìhelpsìinì1ìandì3.ëi¶Thereìareìcasesìwhereì2ìreducesìtoìtheé¶çë?idenï∏„titìyñ≠‡function,ëƒsinceìtheìabstractìsynê∏„taxìisìtheìsameìforìtheìsourceìandìtheé¶çë?targetñ€hlanguageìofìtranslation.ëI#Examplesìforìtheseì\synö∏„tacticìvëˇq«arianòts"ìareìin xé¶çë?andñUUpre xìnotationìforìarithmeticìorìbïGoìoleanëUUexpressions.é¶çëNInñrMgeneral,ëyãtheìsituationìisìmoreìcomplicated.ë»∞Fëˇ*™orìlanguagesìwithìtheìsameé¶çë?expressivï∏„eõPÂpêGoìwìer,ëè…someòtransformationòproïGcessòcanòbìeòde ned.ëdxBetï∏„wìeenòlan-é¶çë?guagesñwithìdi erenö∏„tìexpressivòeìpêGoòwòerìsucòhìaìtransformationìisìnotìalwòaòysìpêGos-é¶çë?sible.ë4 Fõˇ*™orññaìlanguageìthatìisìnotìTòuringìcomplete,ë¶GitìisìnotìpêGossibleìtoìexpressé¶çë?evê∏„eryñcomputation,õ*e.g.ëU`SQLë
  51. cannotìexpressìrcursion,òandìhenceìitìisìnotìpêGossi-é¶çë?bleñ|ëtoìexpressìtheì\ancestor"ìrelationì(whicö∏„hìisìrecursivòelyìde ned).ë)ÜAë|Ztecòhniqueé¶çë?toñBírepresenê∏„tìtransformationìareì\rewriteìruleìsystems".ë9TheìRe neìlanguageé¶çë?conö∏„tainsñÂRaìrewrite-ruleìmecòhanismìinìwhicòhìtheìrulesìareìinìtermsìofìpatternsé¶çë?ofñÌdtheìconcreteìsynö∏„tax.ë9ÙWëˇ*™eìhaòvòeìimplemenòtedìaìrewrite-ruleìsystemìbasedìoné¶çë?tö∏„ypêGedñ@vfeatureìstructures,ë{>calledìœZebu-RR»,ìwhicòhìwillìböGeìdescribòedìinìaìfutureé¶çë?repêGort.éü!ƒççë?ÊAéë\oInstallationéüÁçë?»ThereñUUareìtï∏„wìoõUUwìaìysòtoòinstallòœZebu»:ééüçíÊˇ22ééåãº⁄†l熽ª†'熽¸ççççëMˇˇ éééëX»InstallationñUUusingìŒdefsystemé©çëX»Thisñ#fmakê∏„esìitìeasierìtoìloadìandìcompileìgrammars,ëVÍsinceìoneìdoêGesìnoté§ çëXneedñ“Ûtoìrememê∏„böGerìtheìloòcationìofìaìmoòduleìinìaìdirectoryìstructureìandé°çëXtheñAπparticularìcompilationìandìloadingìfunctions.ë6ÛTëˇ*™oìinstall,ë|“folloê∏„wìtheé°çëXdirectionsñ7inìŒZEBU-sys.l».õVYëˇ*™ouìneedìtheìpêGortableìŒdefsysì»forìthat.òThisìisé°çëXaê∏„vëˇq«ailableñUUasìŒDefsys.tar.Zì»atìtheìsameìplaceìasìŒzebu-???.tar.Z».é¶çëXTheñQ leìŒZEBU-sys.lì»isìusedìtoìloadìorìcompileìœZebu»,ëQıwhicê∏„hìactuallyìcon-é°çëXsistsñUUofìtï∏„wìoñUUsystemsì(de nedìbê∏„yìŒdefsystem»)é©ççíÅ™≥œZebuëhä»theñUUrunê∏„timeìsysteméé°ççíÅ™≥œZebu-compilerëAïk»theëUUcompileréé°¶ççççëMˇˇ éééëX»InstallationñUUwithoutìŒdefsystemé°çëX»Ifñ Zyö∏„ouìdon'tìwòanòtìtoìuseìŒdefsystem»,õ*Ûloadìtheì leìŒCOMPILE-ZEBU.l»,òwhicê∏„hé°çëXcompilesñUUtheìœZebuì» lesìinìtheìrighê∏„tìorder.é§çëXAfterñUUloadingìtheì leìŒZEBU-init.lì»yê∏„ouìcanìcall:é°çëXŒ(zb:zebu)ñUU»toìloadìtheìrunê∏„timeìsystemé§ çëXoré°çëXŒ(zb:zebu-compiler)ñUU»toìloadìtheìgrammarìcompiler.éü!ƒçë?ÊReferenceséüÁçççëD»[1]ééëSé<A.V.ñ?úAhoìandìJ.D.ìUllman.õ™;ÀPrinciplesñîhofìCompilerìDesign».òAddisonë?úWñˇ*™esleyì,é°çëSé<NewñUUYëˇ*™ork,ì1979.é©çççëD[2]ééëSé<CharlesñL*N.ìFiscö∏„herìandìRicòhardìJ.ìLeBlanc.õNÀCrëˇ}'aftingñv˝aìCompiler».òBen-é°çëSé<jamin/Cummings,ñUUMenloìPê∏„ark,ìCA,ì1988.é¶çççëD[3]ééëSé<Micö∏„haelñ9˘R.ìGenesereth.ëIAnìagenòt-basedìframewòorkìforìsoftòwòareìinòterop-é°çëSé<erabilitö∏„yñˇ*™.ë&∫TìecòhnicalñìRepêGortìLogic-92-02,ë¢mDepartmenòtofìComputerìScience,é°çëSé<StanfordõUUUnivï∏„ersitìyëˇ*™,òStanford,ò1992.é¶çççëD[4]ééëSé<Micö∏„haelñ<R.ìGenesereth,ëtKRicòhardìFikòes,ëtKetìal.ë§eKnoòwledgeìinòtercòhangeìformat,é°çëSé<vö∏„ersionñ∑√3.0.ìreferenceìmanòual.ëè$RepöGortìLogic-92-1,ë^LogicìGroupìRepòort,é°çëSé<ComputerñUUScienceìDepartmenö∏„t,ìStanfordìUnivòersitòyëˇ*™,ìStanford,ìJuneì1992.é¶çççëD[5]ééëSé<MarkëùJohnson.ëŸÀAêæìttributeñ^ÕVëˇ;ºalueìLñˇ}'oìgicñ^ÕandìtheìTheõˇ}'oryìofìGròammar».ëŸCenê∏„teré°çëSé<forñUUtheìStudyìofìLanguageìandìInformation,ìStanford,ì1988.é¶çççëD[6]ééëSé<Joacï∏„himõ æLaubscìhòandòDerekòProudian.ë5Aë ∞caseòstudyòinòREFINE:òinìterfac-é°çëSé<ingñPmoöGdulesìviaìlanguages.ë[RepòortìHPL-STL-TM-88-11,ë&ÍHewlettìPï∏„acìkëˇq«ard,é°çëSé<1988.ééüçíÊˇ23ééåã≈Ω†l熽ª†'熽¸çççëD»[7]ééëSé<Billñï™Lewis,õÂøDanìLaLibêGerte,òandìtheìGNUëïXManê∏„ualìGroup.ë)àÀGNUë∫PEmacsé§ çëSé<LispõéRñˇ}'eferìencìeòManual».ëË»Theñ‘ Fõˇ*™reeìSoftï∏„wìareë‘ Fòoundation,õÛ”Camìbridge,òMA,é°çëSé<Decemê∏„bêGerëUU1990.é©çççëD[8]ééëSé<Reasoningñ_7Systems,õêqPê∏„aloìAlto,ò3260ìHillviewìAvê∏„e.,òCAë^˘94304.ë›øÀRëˇ}'e neë±{User'sé°çëSé<Guide»,ëUU1989.é¶çççëD[9]ééëSé<DouglasñÊêR.ìSmith,õ
  52. fiGordonìB.ìKotik,òandìStephenìJ.ìWëˇ*™estfold.ë∏Researcê∏„hé°çëSé<onñì„knoö∏„wledge-basedìsoftòwòareìenòvironmenòtsìatìKESTRELëì”institute.ë)XÀIEEEé°çëSé<Tëˇ;ºrõˇ}'ansactionsñìÁonìSoftwaròeìEngineòering»,ñUUSE-11:1278{1295,ìNoï∏„vìemìbêGerëUU1985.ééüçíÊˇ24ééåãœÖ†l熽ª†'熽¸çë?ÊConïä=tenìtsééüçíÊˇ»25éé寓ÄÉí¿;Ël$ÛPm#ΩRff
  53. cmss10ÛOΔs6ëcmss8ÛN2«@…cmbx8ÛM“o«w        cmss9ÛL÷ΔGÆGÆcmss17Û=D”ÌtGÆGÆcmr17Û;Ú"Vff
  54. cmbx10Û4¬÷N† cmbx12Û/X´Q cmr12Û$m#ΩR
  56. cmss10Û#flÍ<x
  58. cmtt10Û"Ú"V
  60. cmbx10Û ˝':
  62. cmti10Û!",ö
  64. cmsy10Û †b>
  66. cmmi10ÛKÒ`y
  68. cmr10Ût â:        cmbx9Ûo¥ã«        cmr9Û#—fêcmti8Û|{Ycmr8Û 0eórcmmi7Û
  69. Ÿì†Rcmr7ÛπAa®cmr6˘“Áflflflflfl